package com.lw.leetcode.dp.c;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * 1320. 二指输入的的最小距离
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/14 10:01
 */
public class MinimumDistance {

    public static void main(String[] args) {
        MinimumDistance test = new MinimumDistance();

        // 3
//        String word = "CAKE";

        // 6
//        String word = "HAPPY";

        // 15
//        String word = "LVCPBPSGE";

        // 5
//        String word = "LVCP";
//
        //
        String word = Utils.getStr(300, 'A', 'Z');

        int i = test.minimumDistance(word);
        System.out.println(i);
    }


    public int minimumDistance(String word) {
        int length = word.length();
        char[] chars = word.toCharArray();
        for (int i = 0; i < length; i++) {
            chars[i] -= 'A';
        }
        int[][] arr = new int[length + 1][length];
        int size = 26;
        int[][] steps = new int[size][size];
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                steps[i][j] = Math.abs((i / 6) - (j / 6)) + Math.abs((i % 6) - (j % 6));
            }
        }
        for (int i = 2; i <= length; i++) {
            arr[i][0] = arr[i - 1][0] + steps[chars[i - 1]][chars[i - 2]];
            for (int j = 1; j < i; j++) {
                if (i - 1 == j) {
                    int min = arr[j][0];
                    for (int k = 1; k < j; k++) {
                        min = Math.min(min, arr[j][k] + steps[chars[i - 1]][chars[k - 1]]);
                    }
                    arr[i][j] = min;
                } else {
                    arr[i][j] = arr[i - 1][j] + steps[chars[i - 1]][chars[i - 2]];
                }
            }
        }
        int min = Integer.MAX_VALUE;
        for (int anInt : arr[length]) {
            min = Math.min(min, anInt);
        }
        return min;
    }

}
